﻿#pragma once
#include "Index.h"

class IRepeatNumInArr
{
public:
	/**
	 * title: 数组中重复的数字.
	 * keys: 数组 哈希表 排序
	 * https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
	 *
	 * 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
	 * 数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
	 * 请找出数组中任意一个重复的数字。
	 */
	virtual int findRepeatNumber(std::vector<int>& nums) = 0;
};

class RepeatNumInArr
{
public:
	//原地替换法，会修改传入的数组
	class LocalReplace:public IRepeatNumInArr
	{
	public:
		int findRepeatNumber(std::vector<int>& nums) override
		{
			const int numsSize = nums.size();
			for (int i = 0; i < numsSize; ++i)
			{
				while (nums[i] != i)
				{
					int index = nums[i];
					if (nums[index] == index)
						return index;
					std::swap(nums[i], nums[index]);
				}
			}
			throw "no repeat num";
		}
	};

	//二分法，不需要修改传入的数组
	//不正确的解法，不能通过"[2,1,3,1,4]"
	class BinarySplit:public IRepeatNumInArr
	{
	public:
		int findRepeatNumber(std::vector<int>& nums) override
		{
			if (nums.empty())
				return -1;
			
			int left = 0, right = nums.size()-1;
			while(left<right)
			{
				const int mid = (right - left >> 1) + left;
				if (isRepeatInRange(nums, left, mid))
					right = mid;
				else
					left = mid + 1;
			}

			return left;
		}
	private:
		bool isRepeatInRange(std::vector<int>& nums,int sta,int fin)
		{
			const int appeared= findAppearCount(nums, sta, fin);
			const int rangeSize = fin - sta + 1;
			return appeared > rangeSize;
		}
		//查找数字区间[sta,fin]中的数字在nums中出现的总次数
		int findAppearCount(std::vector<int>& nums,int sta,int fin)
		{
			int appeared = 0;
			for(auto& num :nums)
			{
				if (num >= sta && num <= fin)
					appeared++;
			}
			return appeared;
		}
	};
	
	class Review1:public IRepeatNumInArr
	{
	public:
		int findRepeatNumber(std::vector<int>& nums) override
		{
			if (nums.empty())
				return -1;
			const int nums_size = nums.size();
			for(int i=0;i<nums_size;++i)
			{
				while(nums[i]!=i)
				{
					const int goto_index = nums[i];
					if (goto_index == nums[goto_index])
						return nums[goto_index];
					std::swap(nums[i], nums[goto_index]);
				}
			}
			return -1;
		}
	};
};


#ifdef DEV_TEST
#include <gtest/gtest.h>
TEST(RepeatNumInArrTest, findRepeatNumber)
{
	TEST_SOLUTION2(IRepeatNumInArr, RepeatNumInArr::LocalReplace, RepeatNumInArr::BinarySplit, &)
	{
		__slnTestor.setTestTimes(1000);
		const int numSize = 100;

		std::vector<int> nums;
		std::unordered_map<int, int> numsFreq;
		for (int i = 0; i < numSize; ++i)
		{
			const int val = TestingUtil::randIndexInSize(numSize);
			nums.push_back(val);
			numsFreq[val]++;
		}

		const int repeatNum= solution->findRepeatNumber(nums);
		EXPECT_GT(numsFreq[repeatNum], 1)
			<< "nums:" << FormatedUtil::dumpFormated(nums) << std::endl
			<< "repeatNum:" << repeatNum << std::endl;
	};
}
#endif